Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра СКС
Звіт
з лабораторної роботи № 3
з дисципліни: “Дискретна матетематика”
на тему: “ Знаходження максимальної пропускної спроможності графа”
Львів 2013
Мета: навчитися створювати програму яка обчислює максимальну прупускну спроможність графа
Теоретичні відомості
АЛГОРИТМ ФОРДА-ФАЛКЕРСОНА ДЛЯ ЗНАХОДЖЕННЯ ПОТОКУНАЙБІЛЬШОЇ ВЕЛЕЧИНИ
Розглянемо алгоритм Форда на прикладі графа зображеного на мал.1 .
Припустимо, у нас витік буде в 1 вузлі, а стік в 4 вузлі. Алгоритм можна розбити на три кроки:
1.Пошук довільного шляху з витоку до стоку. Якщо такого немає, то видаємо значення максимальної пропускної спроможності і алгоритм завершується.
2.Знаходження в обраному шляху ребра з мінімальною пропускною здатністю. Додаємо значення цього ребра до пропускної спроможності, яка на початку виконання алгоритму дорівнює 0.
3.Віднімання з усіх значень ребер шляху, значення мінімального ребра цього шляху. При цьому саме ребро звернутися в 0 і його вже не можна враховувати в подальшому. Далі продовжуємо з кроку 1.
На початку у нас пропускна здатність дорівнює 0 (P = 0). Припустимо, ми знайшли шлях з витоку 1 в стік 4 через вершини 2 і 3, тобто весь шлях можна записати як (1-2-3-4). У цьому шляху мінімальне ребро з'єднує вершини 2 і 3, його значення 5, збільшуємо пропускну спроможність на 5 (Р = 5). Віднімаємо 5 з ребер з'єднують вершини 1 і 2, 2 і 3, 3 і 4. З вихідного графа у нас випало ребро з'єднує вершини 2 і 3. Вийшов граф зображений на мал.2.
У цьому графі знову шукаємо довільний шлях з 1 в 4. Знайшли (1-2-5-4), де мінімальне ребро з'єднує 2 і 5, його значення 6. Збільшуємо пропускну здатність на 6 (P = 5 +6 = 11). Віднімаємо 6 з усіх ребер шляху, випадає ребро 2-5 (мал.3).
На наступному кроці знаходимо шлях (1-6-5-4), мінімальне ребро 1-6 дорівнює 7, тоді P = 11 +7 = 18. Віднімаємо з ребер шляху 6, при цьому випадає ребро 1-6 і граф розпадається на дві компоненти мал.4.Ми не знаходимо шляху з витоку в стіл і алгоритм завершено. Отримуємо максимальну пропуснну здатність 18 .
Повний потік . Застосовуючи правила 4, 5 алгоритму Форда-Фалкерсона, отримаємо .
Варіант 21
11 18 4 10 7 9 18 19 7 6 5 11 7 9 15 17 19
Код програми:
unit Unit8;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Grids,Math;
type
TForm8 = class(TForm)
Label1: TLabel;
Edit1: TEdit;
Label2: TLabel;
Edit2: TEdit;
Button1: TButton;
StringGrid1: TStringGrid;
Label3: TLabel;
Edit3: TEdit;
Label4: TLabel;
Edit4: TEdit;
Label5: TLabel;
Memo1: TMemo;
procedure FormCreate(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure Edit2Exit(Sender: TObject);
procedure DrawGraph;
procedure DrawLine(a1,a2,c: integer);
procedure FormPaint(Sender: TObject);
procedure StringGrid1SetEditText(Sender: TObject; ACol, ARow: Integer;
const Value: String);
private
{ Private declarations }
public
{ Public declarations }
end;
TMyPoint=record
x:integer;
y:integer;
name:string
end;
const
MaxV=1000;
MaxE=30000;
free_ = 0;
bisy_ = 1;
Great=MaxLongint;
var
Form8: TForm8;
MyPoint:array[1..10] of TMyPoint;
koef:integer;
implementation
{$R *.dfm}
procedure DrawArrowHead(Canvas: TCanvas; X,Y: Integer; Angle,LW: Extended);
var
A1,A2: Extended;
Arrow: array[0..3] of TPoint;
OldWidth: Integer;
const
Beta=0.322;
LineLen=4.74;
CentLen=3;
begi...
